package com.leetcode.problems028;


/**
 * https://leetcode-cn.com/problems/implement-strstr/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution2 {

    /**
     * KMP算法
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        int hl = haystack.length();
        int nl = needle.length();
        if(nl == 0){
            return 0;
        }
        if(hl < nl){
            return -1;
        }
        int[] next = new int[nl];
        int j = 0;
        for (int i = 1; i < nl; i++) {
            if(j > 0 && needle.charAt(i) != needle.charAt(j)){
                j = next[j - 1];
            }

            if(needle.charAt(i) == needle.charAt(j)){
                j = j + 1;
            }
            next[i] = j;
        }
        for (int i = 0,k=0; i<hl;i++) {
            while(k > 0 && haystack.charAt(i) != needle.charAt(k)) {
                k = next[k - 1];
            }
            if(haystack.charAt(i) == needle.charAt(k)){
                k++;
            }
            if(k == nl){
                return i - nl + 1;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        String str = "lo";
        String str1 = "lo";
        System.out.println(new Solution2().strStr(str,str1));
    }
}
